/*
 * @lc app=leetcode.cn id=524 lang=cpp
 *
 * [524] 通过删除字母匹配到字典里最长单词
 *
 * https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting/description/
 *
 * algorithms
 * Medium (49.75%)
 * Likes:    298
 * Dislikes: 0
 * Total Accepted:    83.8K
 * Total Submissions: 168.5K
 * Testcase Example:  '"abpcplea"\n["ale","apple","monkey","plea"]'
 *
 * 给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s
 * 中的某些字符得到。
 *
 * 如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
 * 输出："apple"
 *
 *
 * 示例 2：
 *
 *
 * 输入：s = "abpcplea", dictionary = ["a","b","c"]
 * 输出："a"
 *
 *
 *
 *
 * 提示：
 *
 *
 * 1 <= s.length <= 1000
 * 1 <= dictionary.length <= 1000
 * 1 <= dictionary[i].length <= 1000
 * s 和 dictionary[i] 仅由小写英文字母组成
 *
 *
 */

// @lc code=start
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    bool singleCompare(string s, string &t) {
        int s_len = s.length(), t_len = t.length();
        if (s_len < t_len) {
            return false;
        }
        int s_pos = 0, t_pos = 0;
        while (s_pos < s_len && t_pos < t_len) {
            s[s_pos] == t[t_pos] ? ++s_pos, ++t_pos : ++s_pos;
        }
        return t_pos == t_len ? true : false;
    }
    string findLongestWord(string s, vector<string> &dictionary) {
        string ans{};
        for (auto &word : dictionary) {
            if (singleCompare(s, word)) {
                if(ans.length() !=word.length()){
                    ans = ans.length() > word.length() ? ans : word;
                }else{
                    ans = ans.length() > word.length() ? ans : word;
                }
            }
        }
        return ans;
    }
};
// @lc code=end
